Unique Paths II

LeetCode 63 | Difficulty: Medium

Medium

Problem Description

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The testcases are generated so that the answer will be less than or equal to 2 * 10^9.

Example 1:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

Example 2:

Input: obstacleGrid = [[0,1],[0,0]]
Output: 1

Constraints:

- `m == obstacleGrid.length`

- `n == obstacleGrid[i].length`

- `1 <= m, n <= 100`

- `obstacleGrid[i][j]` is `0` or `1`.

Topics: Array, Dynamic Programming, Matrix

---

Approach

Dynamic Programming

Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

When to use

Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).

Matrix

Treat the matrix as a 2D grid. Common techniques: directional arrays (dx, dy) for movement, BFS/DFS for connected regions, in-place marking for visited cells, boundary traversal for spiral patterns.

When to use

Grid traversal, island problems, path finding, rotating/transforming matrices.

---

Solutions

Solution 1: C# (Best: 328 ms)

Metric	Value
Runtime	328 ms
Memory	N/A
Date	2018-03-06

Solution

public class Solution {
    public int UniquePathsWithObstacles(int[,] obstacleGrid) {
        
int m = obstacleGrid.GetLength(0);
    int n = obstacleGrid.GetLength(1);
    int[,] dp = new int[m+1, n+1];
    dp[0,1]=1;
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {           
            if(obstacleGrid[i-1,j-1]!=1)
            {
                dp[i, j] = dp[i - 1, j] + dp[i, j - 1];
            }           
        }
    }
    return dp[m, n];


}
}

---

Complexity Analysis

Approach	Time	Space
DP (2D)	$O(n × m)$	$O(n × m)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
• Consider if you can reduce space by only keeping the last row/few values.
• LeetCode provides 2 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Use dynamic programming since, from each cell, you can move to the right or down.

Hint 2: assume dp[i][j] is the number of unique paths to reach (i, j). dp[i][j] = dp[i][j -1] + dp[i - 1][j]. Be careful when you encounter an obstacle. set its value in dp to 0.